package ch4tree;

import java.util.LinkedList;
import java.util.Stack;

public class GraphAlgorithms {

	public static boolean breathFirstSearch(Graph g, GraphNode start, GraphNode end) {
		if (start == end) {
			return true;
		}
		
		for (GraphNode node : g.getNodes()) {
			node.state = State.Unvisited;
		}
		
		LinkedList<GraphNode> queue = new LinkedList<>();
		queue.offer(start);
		start.state = State.Visiting;
		while (!queue.isEmpty()) {
			GraphNode head = queue.poll();
			for (GraphNode n : head.getAdjacent()) {
				if (n == end) {
					return true;
				}
				
				if (n.state == State.Unvisited) {
					queue.offer(n);
					n.state = State.Visiting;
				}
			}
			head.state = State.Visited;
		}
		return false;
	}

	public static boolean depthFirstSearch(Graph g, GraphNode start, GraphNode end) {
		if (start == end) {
			return true;
		}
		
		for (GraphNode node : g.getNodes()) {
			node.state = State.Unvisited;
		}
		
		Stack<GraphNode> stack = new Stack<>();
		stack.push(start);
		start.state = State.Visiting;
		while (!stack.isEmpty()) {
			GraphNode pop = stack.pop();
			for (GraphNode n : pop.getAdjacent()) {
				if (n == end) {
					return true;
				}
				else if (n.state == State.Unvisited) {
					n.state = State.Visiting;
					stack.push(n);
				}				
			}
			pop.state = State.Visited;
		}
		return false;
	}
	
	public static boolean recursiveDFS(Graph g, GraphNode start, GraphNode end) {
		if (start == end) {
			return true;
		}
		
		for (GraphNode node : g.getNodes()) {
			node.state = State.Unvisited;
		}

		return visitDFSRecurse(start, end);
	}

	private static boolean visitDFSRecurse(GraphNode u, GraphNode v) {
		u.state = State.Visiting;
		for (GraphNode w : u.adjacent) {
			if (w == v) {
				return true;
			}
			
			if (w.state != State.Unvisited) {
				continue;
			}
			
			boolean found = visitDFSRecurse(w, v);
			if (found) {
				return true;
			}
		}
		u.state = State.Visited;
		return false;
	}
}
